package com.datastructures2.graph.最短路径;

import com.datastructures2.graph.有向图.TopologicalSort;
import edu.princeton.cs.algs4.Stack;

/**
 * 加权有向无环图的最短路径算法(使用拓扑排序)
 * @author MaoLin Wang
 * @date 2020/2/2413:48
 */
public class AcyclicSP {
    private DirectedEdge[] edgeTo;
    private double[] distTo;
    public AcyclicSP(EdgeWeightedDigraph digraph,int s){
        edgeTo=new DirectedEdge[digraph.V()];
        distTo=new double[digraph.V()];

        for (int v=0;v<digraph.V();v++){
            distTo[v]=Double.POSITIVE_INFINITY;
        }
        distTo[s]=0.0;

        TopologicalSort sort=new TopologicalSort(digraph);
        if (!sort.hasOrder()){
            throw new IllegalArgumentException("Digraph is not acyclic.");
        }
        for(int v:sort.order()){
            relax(digraph,v);
        }
    }

    private void relax(EdgeWeightedDigraph digraph, int v) {
        for (DirectedEdge edge:digraph.adj(v)){
            int to=edge.to();
            if (distTo[to]>distTo[v]+edge.weight()){
                distTo[to]=distTo[v]+edge.weight();
                edgeTo[to]=edge;
            }
        }
    }
    public double distTo(int v){
        return distTo(v);
    }
    public boolean hasPathTo(int v){
        return distTo(v)<Double.POSITIVE_INFINITY;
    }

    public Iterable<DirectedEdge> pathTo(int v){
        Stack<DirectedEdge> path=new Stack<>();
        for ( DirectedEdge edge=edgeTo[v]; edge!=null ; edge=edgeTo[edge.from()]) {
            path.push(edge);
        }
        return path;
    }

    public static void main(String[] args) {
        int[] j=new int[]{0};
        for (int i = 0; i < 10000; i++) {
            new Thread(()->{
                j[0]++;
            }).start();;
        }
        System.out.println(j[0]);
    }
}
